package com.practice.niuke.new_direct_basics.class08;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * 打印一个字符串的全部排列
 * 打印一个字符串的全部排列， 要求不要出现重复的排列
 */
public class Code03_PrintAllPermutations {

    /**
     * 收集一个字符串的全排列字符串（TODO：标记主函数）
     *
     * @param s 字符串
     * @return List<String>
     */
    public static List<String> getAllC(String s) {
        List<String> ans = new ArrayList<>();
        // 把字符串s中的所有字符都放到一个List集合里面去（避免重复字符）
        ArrayList<Character> set = new ArrayList<>();
        for (char cha : s.toCharArray()) {
            set.add(cha);
        }
        // process1(set, "", ans);
        process(set, "", ans);
        return ans;
    }

    /**
     * 收集“字符数组”所表示的字符串的所有字符全排列后的结果。（不允许出现重复排列）
     * List中的所有字符都可以选择，
     * 形成的所有全排列放入ans，
     * 沿途的决定就是path
     *
     * @param set  字符串中的所有字符都放到一个List集合里面去后的Set集合
     * @param path
     * @param ans  存储全排列结果的集合
     */
    public static void process(ArrayList<Character> set, String path, List<String> ans) {
        if (set.isEmpty()) {
            ans.add(path);
            return;
        }
        // 当前已经挑选过的字符
        HashSet<Character> picks = new HashSet<>();
        // List中每一个字符都可以作为当前字符，但是一旦当前决定要，后续就不能再使用了
        for (int index = 0; index < set.size(); index++) {
            // 如果当前字符没有被挑选过
            if (!picks.contains(set.get(index))) {
                // 选择要当前字符，将当前字符放入picks中
                picks.add(set.get(index));
                String pick = path + set.get(index);
                // 拷贝原来的“总”字符集合
                ArrayList<Character> next = new ArrayList<>(set);
                // 将“总”字符集合中当前使用的字符去掉
                next.remove(index);
                process(next, pick, ans);
            }
        }
    }

    /**
     * 收集“字符数组”所表示的字符串的所有字符全排列后的结果。（允许出现重复排列）
     * List中的所有字符都可以选择，
     * 形成的所有全排列放入ans，
     * 沿途的决定就是path
     *
     * @param set  字符串中的所有字符都放到一个List集合里面去后的List集合
     * @param path
     * @param ans  存储全排列结果的集合
     */
    public static void process1(ArrayList<Character> set, String path, List<String> ans) {
        if (set.isEmpty()) {
            ans.add(path);
            return;
        }
        // List中每一个字符都可以作为当前字符，但是一旦当前决定要，后续就不能再使用了
        for (int index = 0; index < set.size(); index++) {
            // 选择“要”当前字符
            String pick = path + set.get(index);
            // 拷贝原来的“总”字符集合
            ArrayList<Character> next = new ArrayList<>(set);
            // 将“总”字符集合中当前使用的字符去掉
            next.remove(index);
            process(next, pick, ans);
        }
    }

    public static void main(String[] args) {
        String s = "aac";
        List<String> ans = getAllC(s);
        for (String str : ans) {
            System.out.println(str);
        }
    }

}
